package demo.practice.tree;


import demo.practice.TreeNode;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

public class P449 {


    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuffer sb = new StringBuffer();
        serialize(root, sb);
        System.out.println(sb.toString());
        return sb.toString();
    }

    public void serialize(TreeNode root, StringBuffer sb) {
        sb.append(root == null ? "#" : root.val);
        sb.append(",");
        if (root != null) {
            serialize(root.left, sb);
            serialize(root.right, sb);
        }
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] split = data.split(",");
        Queue<String> queue = new LinkedList<>();
        for (String s : split) {
            queue.add(s);
        }

        return deserialize(queue);
    }


    public TreeNode deserialize(Queue<String> queue) {
        if (queue.size() > 0) {
            if (!queue.peek().equals("#")) {
                TreeNode root = new TreeNode(Integer.parseInt(queue.peek()));
                queue.poll();
                root.left= deserialize(queue);
                root.right= deserialize(queue);
                return root;
            } else {
                queue.poll();
            }
        }

        return null;
    }

}
